The present invention relates to network communication, and more specifically, to apparatuses, methods and systems for enhancing quality of service in a network.
In the current state of the Internet, the issues of guaranteed bandwidth fairness and support for multiple levels of latency are becoming increasingly important. Guaranteed bandwidth fairness is typically provided using so called xe2x80x9cFair Queuingxe2x80x9d algorithms. These algorithms guarantee that bandwidth of a certain link (or virtual link) is fairly apportioned among its various flows. Fair Queuing algorithms are incorporated into network systems using fair queuing (or bandwidth) schedulers. These schedulers seek to control congestion even in the presence of ill-behaved sources, so that a single source that sends packets to a gateway at a sufficiently high speed cannot capture an arbitrarily high portion of the bandwidth of the outgoing line. While providing bandwidth guarantees is important, it is also important that latency-critical traffic flows (such as Voice Over IP and Video) experience as low latency as possible. Prioritizing traffic flows so that latency-critical flows experience low latency is currently provided by priority (or latency) schedulers.
Conventional network solutions have attempted to resolve both fair queuing and priority scheduling, and, despite the inherent tension between the two concerns, have been somewhat successful in incorporating both features in network systems. For instance, according to one conventional solution shown in FIG. 1, conventional schedulers 120 have been created that cascade both fair queuing 100 and priority schedulers 110 in series to achieve fair queuing and low latency for latency-critical traffic. Fair queuing schedulers 100 have been proposed in which gateways maintain separate queues for packets received from each individual source. In many fair queuing schedulers, the queues are then serviced in a round-robin manner, which prevents a source from arbitrarily increasing its share of bandwidth or the delay of other sources. Therefore, when a source sends packets too quickly, it may effectively lengthen its own queue, thereby preventing anti-social behavior and limiting the negative impact on well-behaved sources. Other schedulers, some of which use a round-robin-based approach, have attempted to resolve problematic sources that send very long packets of data, which can get more bandwidth than other sources. However, these attempts suffer from some disadvantages, including that cascading the schedulers often results in erroneous queuing. Furthermore, arrangements such as those illustrated in FIG. 1 can require a substantial amount of packet processing.
One method for maintaining quality of service for networks, Deficit Round Robin (DRR), is a well-known fair queuing algorithm that is relatively efficient, simple, and is increasingly being accepted as a standard for fair queuing. DRR guarantees fair apportioning of bandwidth, provides close-to-perfect fairness in scheduling, and provides fast and lightweight enqueuing and dequeuing operations. DRR also provides O(1) time complexity, which means that the algorithm""s computation does not grow with input size (the number of queues). As a result, the processing time taken by the algorithm is independent of the number of queues. DRR is next explained in detail with reference to prior art FIGS. 2, 3A and 3B, although it should be appreciated that DRR is well known to those of skill in the art.
FIG. 2 shows a DRR queue structure 200 implemented by the DRR algorithm. The DRR queue structure 200 is located between an incoming link 210 and an outgoing link 220, and operates to buffer data packets. Incoming packets from data sources received via the incoming link 210 are queued in the DRR queue structure 200 by an enqueue agent 230. The enqueue agent 230 typically creates a queue for each source forwarding data packets over the incoming link. According to one embodiment of DRR, queues are created and ordered sequentially based on the time data packets arrive at the queue structure 200. Therefore, a first data packet from a first source may be buffered into a first queue position in the queue structure 200, whereas a later received data packet from a separate source may be placed in a queue positioned lower in the queue structure 200. After the packets are queued onto the DRR queue structure 200, a dequeue agent 240 removes the packets from the DRR queue structure 200 and transmits the packets over the outgoing link 220. The implementations of the enqueue agent 220 and dequeue agent 240 constitute the DRR queuing algorithm. According to DRR queuing, the dequeue agent 240 intelligently dequeues the packets from the DRR queue structure 200 based on bandwidth apportioning specifications and places the packets on the outgoing link. One implementation of the DRR queue structure 200 consists of an array of linked lists of packets, which ensures that each queue (for example, the nth queue) can be accessed quickly. Additionally, the head and tail pointers of the linked list are stored so as to enable sufficient enqueuing and dequeuing.
According to one implementation of DRR, there is typically a deficit 250 data element and a quota 260 data element. According to the DRR algorithm, each data flow that is assured a share of bandwidth has a corresponding first in first out queue inside the DRR, and each queue within the DRR queue structure 200 has a deficit and quota associated therewith. The quota 260 data element of a queue is the number of bytes of data the queue will send per cycle when viewed from a long-term average. The deficit 250 refers the number of bytes of data that a queue can send in the current round. According to a general weighted variant of DRR, the quotas of the various queues of the DRR are initially set so that the ratios of the quotas are in accordance with the intended apportioning of bandwidth among flows. However, in the example presented in FIG. 3., all quotas are equal and hence coalesced into a single data element termed Quantum. One skilled in the art would appreciate that in the most general case, each queue would have its corresponding quota. In operation, the enqueue agent 230 enqueues an arriving packet into the packet""s appropriate queue. The dequeue agent 240 then continuously steps through the queues in a round-robin fashion and sends as many packets from a queue as allowed by its deficit. At the end of each round, the deficit of a non-empty queue is increased by the quantum (and in the most general case, by its quota), as maintained in the quota element. Thus, if a packet cannot be sent for want of deficit, that remaining deficit is retained and increased by its quota in the next round. As a result, past unfairness due to packet boundaries is corrected in subsequent rounds. However, it should be appreciated that queues that are empty (i.e., have no packets located therein) at the end of the round do not retain and add their current deficit to that of the next round. The past deficit is then ignored since it was not being made use of and hence did not cause any unfairness.
The operation of DRR is illustrated in FIGS. 3a and 3b, which show a queue structure having four queues 310, labeled 1 through 4, where each queue has buffered a plurality of packets. As referred to herein, the fourth queue, labeled queue #4, has a greater queue number than queues one through three. For instance, in FIG. 3a, the first queue (labeled queue #1) includes packets having 200, 750 and 20 data elements (e.g., each data element is a byte of data), while the second queue (labeled queue #2) includes packets of 500 and 500 data elements. The packets are buffered in each respective queue sequentially, such that the packets arriving first enter the queue before packets arriving later in time. For instance, in the first queue of FIG. 3a, the packet having 200 data elements is first in the queue because it arrived before those packets sized at 750 and 20 data elements. Similarly, the packet having 750 data elements is second in the queue because it arrived before the packet sized at 20 data elements. Because DRR operates on a first in first out basis within each queue, the packet that enters the queue earliest in time is the first packet that will be dequeued and transmitted over an outgoing link. Also illustrated in FIGS. 3a and 3b is a deficit counter 320 for maintaining the current deficit, as explained earlier. At the beginning of each round, non-empty queues have their deficit counters increased by the Quantum, whereas empty queues have their deficit counters set to the Quantum. In this example of DRR there is no notion of a per-queue quantum or quota, but rather a global quantum that applies to all queues. However, a variant of DRR (which is usually termed weighted DRR) has queue-specific quotas. Referring again to FIG. 3a, the value of the deficit counter 320 establishes the number of units of data that will be dequeued from the corresponding queue by the dequeue agent during a current round of the deficit round robin process.
FIG. 3a shows the state of the queue structure during an initial state of the DRR operation. In this state, a round robin pointer (or dequeue agent) 340 initially points to the first queue within the queue structure. The deficit counter 320 shows a value of 500 data elements in FIG. 3a because the quantum size 330 is added to the queue""s current deficit maintained by the deficit counter 320, which is initially zero for each individual queue in the present illustration. However, it will be appreciated by those of skill in the art that the deficit counter 320 can alternatively be initially set at any value for each queue. After the quantum size 330 (500) is added to the deficit counter 320, the first packet of data buffered by the first queue, sized at 200 data elements, is compared to the data element value maintained in the deficit counter 320 that corresponds to the first queue (500). Because the deficit counter 320 contains a data element value equal to or greater than the number of data elements in the packet (500 greater than 200), the packet is removed from the queue structure by the dequeue agent and transmitted over an outgoing link. The deficit counter is then reduced by the number of data elements within the transmitted packet. Because the transmission of the packet did not utilize the first queue""s entire allotment of deficit (500xe2x88x92200=300), the next packet in the first queue is then compared in the same manner as the first to the new value of the deficit counter, and this process is repeated until the deficit counter has insufficient deficit to transmit a packet.
Continuing with the illustrative example shown in FIG. 3a, the value of the deficit counter is reduced to 300 after the first packet is transmitted. Repeating the steps discussed above in processing the first packet, the DRR algorithm compares the new, reduced deficit counter 320 value to the size of the next packet, which has 750 data elements. Because the deficit counter 320 value is not greater than or equal to the size of the packet, the packet is not transmitted over the outgoing link, thereby preventing the source populating the first queue from utilizing a disproportionate share of the outgoing link bandwidth. However, as illustrated in FIG. 3b, the deficit counter 320 retains the unused allocation of data elements (300), which remain in the deficit counter 320 for use by the first queue during the next transmission attempt. Thereafter, the round robin pointer 340 moves to the second queue in the queue structure, and repeats the steps described above with respect to the first queue.
The DRR algorithm repeats the above steps by continuously stepping through the queues in a round-robin fashion, sending as many packets from each queue as allowed by its deficit and the quantum size. For instance, when the round robin pointer selects the first queue during the second round, the quantum size (500) will be added to the deficit (300), yielding a total of 800 data elements in the deficit counter 320. Therefore, the packet with 750 data elements and the packet with 20 data elements will both be dequeued and transmitted out an outgoing link, because 800 greater than (750+20).
In sum, DRR in its most general form arranges each queue to have an associated bandwidth, quota and down counted deficit, where the deficit is the amount of data a queue can send in the current round. The deficit keeps track of past unfairness and each queue""s quota is added to its deficit at the beginning of each round. The queues send packets on a round robin basis, and a packet is sent from the queue only when the queue has sufficient deficit. When a packet is sent from the queue its size is subtracted from the deficit. If a packet is unable to be sent due to insufficient deficit, the remaining deficit is added to the next round""s deficit, thereby correcting unfairness in subsequent rounds. Finally, it should be appreciated that the worst case cycle time in DRR is proportional to the sum of the queue bandwidth quotas divided by the bandwidth.
Although DRR is relatively efficient, simple, and is increasingly being accepted as a standard for fair queuing, DRR suffers from a number of problems that are undesirable for fair queuing of all types of traffic. For instance, DRR can cause packets to suffer high latency, causing DRR to be unsuitable for latency critical flows, such as Voice Over IP. DRR also does not have mechanisms for handling multiple levels of latency critical flows. Additionally, DRR is a fair bandwidth scheduler, rather than a prioritized latency scheduler.
Therefore, it will be appreciated that it would be advantageous to have a fair queuing and priority scheduling solution providing multiple levels of latency. It would also be advantageous to incorporate both fair queuing and priority scheduling, to work in unison and overcome latency-related problems associated with DRR. It would also be advantageous to implement both features to provide a fair bandwidth prioritized latency scheduler rather than merely a fair bandwidth scheduler, as is provided by DRR.
According to one embodiment of the present invention, there is provided an Integrated Bandwidth Latency Scheduler apparatus, method and system (collectively referred to herein as IBLS) that combines Fair Queuing and Priority Schedulers in a single stage to provide bandwidth fairness guarantees as well as latency prioritization. The IBLS accomplishes these goals by providing a scheduler and process that dequeues packets from multiple queues in an order based upon an algorithm of the IBLS that arranges and dequeues those queues having the highest priority based on content therein. However, the systems, methods and apparatuses of the present invention also utilize quotas and deficit counters, similar to the DRR process described above, to ensure that packets from each source receive their fair portion of the outgoing link bandwidth. To determine which first in first out queue an incoming data packet is placed, the enqueue agent utilized by the present invention classifies incoming packets based on the type of data included within the data packet, the source of the packet, the type of data flow, or another attribute of the packet, such as a header associated with the packet.
IBLS obviates the need for two stages of queuing to achieve both bandwidth and priority-based scheduling and thus reduces per-packet latency. By means of a novel way of dequeuing packets, IBLS ensures that latency critical flows experience a lower latency than other flows. While doing so, IBLS makes sure that bandwidth fairness is not compromised. To achieve this, it ensures that both bandwidth scheduling and prioritized latency scheduling work in unison without causing correctness problems. The bandwidth scheduler functionality within the IBLS decides how many packets are allowable from each queue in the current round, whereas the priority scheduler functionality makes sure that among these packets, those of higher latency critically get sent earlier. Furthermore, under typical loads, the IBLS of the present invention provides a significant amount of latency differentiation over conventional scheduling algorithms such as DRR. IBLS reduces jitter of high priority flows under usual loads. IBLS also provides better bandwidth fairness than DRR on a per cycle (i.e. round) basis. The latency differentiation effect of IBLS diminishes in times of extreme congestion. And IBLS not only avoids queuing-theoretic flaws introduced by a two-stage design, but also reduces the latency experienced by a packet. Therefore, the IBLS approach is of great benefit in systems that need both bandwidth fairness and latency differentiation.
Also provided in the present invention is a weighted fair queuing algorithm providing express paths to latency critical components of aggregated flows while providing bandwidth guarantees to aggregated user flows. Therefore, although aggregated user flows may consist of traffic components of varying importance, the present invention makes it is possible to isolate and provide a lower latency to latency critical components of such aggregated user flows, while still ensuring that all aggregated flows still experience their overall share of fair bandwidth. The latency critical components of aggregated flows can be separated and placed in a latency critical queue while the non-latency-critical components of aggregated flows use non-latency-critical queues corresponding to their respective user flows. The dedicated queues and bandwidth borrowing features of the present invention apportion link bandwidth among users, ensure fair sharing of extra bandwidth among various users, and provide fast paths for latency critical application flows.